package ods;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;

/**
 * An implementation of linear probing.  The hash method used is tabulation hashing.
 *
 * @param <T>
 * @author morin
 */
public class LinearHashTable<T> implements USet<T> {

    protected static final int w = 32;
    protected static final int r = 8;
    Factory<T> f;

    /**
     * The table
     */
    T[] t;   // the table

    /**
     * Special marker - used to show deleted nodes
     */
    T del;

    int n;   // the size
    int d;   // t.length = 2^d
    int q;   // number of non-null entries in t

    /**
     * @param nil an object of class T that will never be
     *            stored in the table
     */
    @SuppressWarnings("unchecked")
    public LinearHashTable(T nil) {
        this.del = nil;
        f = new Factory<T>((Class<T>) nil.getClass());
        d = 1;
        t = f.newArray(1 << d);
    }

    /**
     * Resize the backing array to have size 2^d
     * Warning: 2^d should be much bigger than n
     *
     * @param d
     */
    protected void resize() {
        d = 1;
        while ((1 << d) < 3 * n) d++;
        T[] told = t;
        t = f.newArray(1 << d);
        q = n;
        // insert everything from told
        for (int k = 0; k < told.length; k++) {
            if (told[k] != null && told[k] != del) {
                int i = hash(told[k]);
                while (t[i] != null)
                    i = (i == t.length - 1) ? 0 : i + 1;
                t[i] = told[k];
            }
        }
    }

    protected int hash(T x) {
        int h = x.hashCode();
        return (tab[0][h & 0xff]
                ^ tab[1][(h >>> 8) & 0xff]
                ^ tab[2][(h >>> 16) & 0xff]
                ^ tab[3][(h >>> 24) & 0xff])
                >>> (w - d);
    }

	/* sample code
	protected int idealHash(T x) {
		return tab[x.hashCode() >>> w-d];
	}
	*/

/*  this code is broken - repeatedly adding and removing the same element gives a big chain
	public boolean addSlow(T x) {
		if (2*(q+1) > t.length) resize(); // max 50% occupancy
		int i = hash(x);
		while (t[i] != null) {
			if (t[i] != del && x.equals(t[i])) return false;
			i = (i == t.length-1) ? 0 : i + 1; // increment i
		}
		t[i] = x;
		n++; q++;
		return true;
	}
	*/

    public boolean add(T x) {
        if (find(x) != null) return false;
        if (2 * (q + 1) > t.length) resize(); // max 50% occupancy
        int i = hash(x);
        while (t[i] != null && t[i] != del)
            i = (i == t.length - 1) ? 0 : i + 1; // increment i
        if (t[i] == null) q++;
        n++;
        t[i] = x;
        return true;
    }

    /**
     * A faster version of add(x)
     *
     * @param x
     * @return
     */
    public boolean add2(T x) {
        if (2 * (q + 1) > t.length) resize(); // max 50% occupancy
        int i = hash(x), j = -1;
        while (t[i] != null) {
            if (t[i] == del && j == -1) j = i;
            if (t[i] != del && t[i].equals(x)) return false;
            i = (i == t.length - 1) ? 0 : i + 1; // increment i
        }
        t[j == -1 ? i : j] = x;
        n++;
        q++;
        return true;
    }


    public T find(T x) {
        int i = hash(x);
        while (t[i] != null) {
            if (t[i] != del && x.equals(t[i])) return t[i];
            i = (i == t.length - 1) ? 0 : i + 1; // increment i
        }
        return null;
    }

    public T remove(T x) {
        int i = hash(x);
        while (t[i] != null) {
            T y = t[i];
            if (y != del && x.equals(y)) {
                t[i] = del;
                n--;
                if (8 * n < t.length) resize(); // min 12.5% occupancy
                return y;
            }
            i = (i == t.length - 1) ? 0 : i + 1;  // increment i
        }
        return null;
    }

    public int size() {
        return n;
    }

    public void clear() {
        n = 0;
        q = 0;
        d = 1;
        t = f.newArray(1 << d);
    }

    public Iterator<T> iterator() {
        class IT implements Iterator<T> {
            int i, iprev;

            public IT() {
                iprev = -1;
                i = 0;
                while (i < t.length && (t[i] == null || t[i] == del)) i++;
            }

            public boolean hasNext() {
                return i < t.length;
            }

            public T next() {
                T x = t[i];
                iprev = i;
                while (i < t.length && (t[i] == null || t[i] == del)) i++;
                return x;
            }

            public void remove() {
                t[iprev] = del;
                n--;
            }
        }
        ;
        return new IT();
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Random rand = new Random(1);
        USet<Integer> lht = new LinearHashTable<Integer>(-1);
        Set<Integer> s = new HashSet<Integer>();
        int n = 1000000;
        System.out.println("Adding");
        for (int i = 0; i < n; i++) {
            Integer x = rand.nextInt(n);
            boolean rs = s.add(x);
            boolean rlht = lht.add(x);
            if (rs != rlht)
                throw new RuntimeException("Aaaaaaaaaaaaaaaah!");
            if (s.size() != lht.size()) {
                System.out.println(s.size());
                System.out.println(lht.size());
                throw new RuntimeException("Bwaaaaaaaaaaaaaaah!");
            }
        }
        System.out.println("Searching");
        for (int i = 0; i < n; i++) {
            Integer x = rand.nextInt(n);
            boolean rs = s.contains(x);
            boolean rlht = lht.find(x) != null;
            if (rs != rlht)
                throw new RuntimeException("Aaaaaaaaaaaaaaaah!");
            if (s.size() != lht.size())
                throw new RuntimeException("Bwaaaaaaaaaaaaaaah!");
        }

        System.out.println("Removing");
        for (int i = 0; i < n; i++) {
            Integer x = rand.nextInt(n);
            boolean rs = s.remove(x);
            boolean rlht = lht.remove(x) != null;
            if (rs != rlht)
                throw new RuntimeException("Aaaaaaaaaaaaaaaah!");
            if (s.size() != lht.size())
                throw new RuntimeException("Bwaaaaaaaaaaaaaaah!");
        }
        s.clear();
        lht.clear();
    }

    /**
     * Table used by tabular hashing
     */
    protected static int[][] tab =
            {{0x0069aeff,
                    0x6ac0719e,
                    0x384cd7ee,
                    0xcba78313,
                    0x133ef89a,
                    0xb37979e6,
                    0xa4c4e09c,
                    0x911c738b,
                    0xc7fe9194,
                    0xba8e5dc7,
                    0xe610718c,
                    0x48460ac5,
                    0x6b4d9d43,
                    0x73afeeab,
                    0x051264cb,
                    0x4b3dba93,
                    0x28837665,
                    0xfb80a52b,
                    0xad1c14af,
                    0xb2baf17f,
                    0x35e311a5,
                    0xf7fa2905,
                    0xa973c315,
                    0x00885f47,
                    0x8842622b,
                    0x0445a92c,
                    0x701ba3a0,
                    0xef608902,
                    0x176099ad,
                    0xd240f938,
                    0xb32d83c6,
                    0xb341afb8,
                    0xc3a978fb,
                    0x55ed1f0c,
                    0xb581286e,
                    0x8ff6938e,
                    0x9f11c1c5,
                    0x4d083bd6,
                    0x1aacc2a4,
                    0xdf13f00a,
                    0x1e282712,
                    0x772d354b,
                    0x21e3a7fd,
                    0x4bc932dc,
                    0xe1deb7ba,
                    0x5e868b8a,
                    0xc9331cc6,
                    0xaa931bbf,
                    0xff92aba6,
                    0xe3efc69f,
                    0xda3b8e2a,
                    0xf9b21ec1,
                    0x2fb89674,
                    0x61c87462,
                    0xa553c2f9,
                    0xca01e279,
                    0x35999337,
                    0xf44c4fd3,
                    0x136a2773,
                    0x812607a8,
                    0xbfcd9bbf,
                    0x0b1d15cd,
                    0xc2a0038b,
                    0x029ab4f7,
                    0xcd7c58f9,
                    0xed3821c4,
                    0x325457c6,
                    0x1dc6b295,
                    0x876dcb83,
                    0x52df45fc,
                    0xa01c9fba,
                    0xc938ff66,
                    0x19e52c87,
                    0x03ae67f9,
                    0x7db39e51,
                    0x74f31686,
                    0x5f10e5a3,
                    0x74108d8a,
                    0x64e63104,
                    0xd86a38d6,
                    0x65be2fbb,
                    0xef06049e,
                    0x9bca1dbd,
                    0x06c63e73,
                    0xe97bd103,
                    0xfed3c22c,
                    0x09d10fc6,
                    0xb92633a3,
                    0x21378ebf,
                    0xe37fa54e,
                    0x893c7910,
                    0xc1c74a5a,
                    0x6c23c029,
                    0x4d4b6187,
                    0xd72bb8fb,
                    0x0dbe1118,
                    0x5e0f4188,
                    0xce0d2dc8,
                    0x8dd83231,
                    0x0466ab90,
                    0x814bc11a,
                    0xef688b9b,
                    0x0a03c851,
                    0xca3c984f,
                    0x6df87ca4,
                    0x6b34d1b2,
                    0x2bad5c75,
                    0xaed1b6d8,
                    0x8c73f8b4,
                    0x4577d798,
                    0x5c953767,
                    0xe7da2d51,
                    0x2b9279a0,
                    0x418d9b51,
                    0x8c47ec3d,
                    0x894e6119,
                    0xa0ca769d,
                    0x1c3b16a4,
                    0xa1621b5b,
                    0xa695da53,
                    0x22462819,
                    0xf4b878cf,
                    0x72b4d648,
                    0x1faf4267,
                    0x4ba16750,
                    0x08a9d645,
                    0x6bfb829c,
                    0xe051295f,
                    0x6dd5cd97,
                    0x2e9d1baf,
                    0x6ed6231d,
                    0x6f84cb25,
                    0x9ae60c95,
                    0xbcee55ca,
                    0x6831cd97,
                    0x2ccdbc99,
                    0x9f8a0a81,
                    0xa0b2c08f,
                    0xe957c36b,
                    0x9cb797b5,
                    0x107c6362,
                    0x48dacf5d,
                    0x6e16f569,
                    0x39be78c3,
                    0x6445637f,
                    0xed445ee5,
                    0x8ec45004,
                    0x9ef8a405,
                    0xb5796a45,
                    0x049d5143,
                    0xb3c1d852,
                    0xc36d9b44,
                    0xab0da981,
                    0xff5226b3,
                    0x19169b4c,
                    0x9a49194d,
                    0xba218b42,
                    0xab98c8ee,
                    0x4db02645,
                    0x6faca3c8,
                    0x12c60d2d,
                    0xaf67b750,
                    0xf0f6a855,
                    0xead566d9,
                    0x42d0cccd,
                    0x76a532bb,
                    0x82a6dc35,
                    0xc1c23d0e,
                    0x83d45bd2,
                    0xd7024912,
                    0x97888901,
                    0x2b7cdd2c,
                    0x523742a5,
                    0xecb96b3b,
                    0xd800d833,
                    0x7b4d0c91,
                    0x95c7dd86,
                    0x88880aad,
                    0xf0ce0990,
                    0x7e292a90,
                    0x79ac4437,
                    0x8a9f59cc,
                    0x818444d1,
                    0xae4e735d,
                    0xa529db95,
                    0x58b35661,
                    0xa909a7de,
                    0x9273beaa,
                    0xfe94332c,
                    0x259b88e4,
                    0xc88f4f6a,
                    0x2a9d33ef,
                    0x4b5d106d,
                    0xdc3a9fca,
                    0xa8061cad,
                    0x7679422c,
                    0xaf72ad02,
                    0xc5799ea5,
                    0x306d694d,
                    0x620aad10,
                    0xd188b9dd,
                    0xeff6ad87,
                    0x6b890354,
                    0xb5907cd3,
                    0x733290fc,
                    0x4b6c0733,
                    0x0bad0ebd,
                    0xa049d3ad,
                    0xc9d0cdae,
                    0x9c144d6f,
                    0x5990b63b,
                    0xfa33d8e2,
                    0x9ebeb5a0,
                    0xbc7c5c92,
                    0xd3edd2e6,
                    0x54ae1af6,
                    0xd6ada4bd,
                    0x14094c5a,
                    0x0e3c5adf,
                    0xf1ab60f1,
                    0x74456a66,
                    0x0f3a675a,
                    0x87445d0d,
                    0xa81adc2e,
                    0x0f47a1a5,
                    0x4eedb844,
                    0x9c9cb0ce,
                    0x8bb3d330,
                    0x02df93e6,
                    0x86e3ad51,
                    0x1c1072b9,
                    0xacf3001b,
                    0xbd08c487,
                    0xc2667a11,
                    0xdd5ef664,
                    0xd47b67fb,
                    0x959cca45,
                    0xa7da8e68,
                    0xb75b1e18,
                    0x75201924,
                    0xe689ab8b,
                    0x0f5e6b0a,
                    0x75205923,
                    0xbba35593,
                    0xd24dab24,
                    0x0288caeb,
                    0xcbf022a9,
                    0x392d7ee5,
                    0x16fe493a,
                    0xb6bcadfd,
                    0x9813ec72,
                    0x9aa3d37c,
                    0xee88a59e,
                    0x6cdbad4e,
                    0x6b96aabf,
                    0xcb54d5e5},
                    {0x116fc403,
                            0x260d7e7b,
                            0xdef689e7,
                            0xa5b3d49a,
                            0x921f3594,
                            0xb24c8cba,
                            0x1bdefb3f,
                            0x6519e846,
                            0x24b37253,
                            0x1cc6b12b,
                            0x6f48f06e,
                            0xca90b0db,
                            0x8e20570b,
                            0xda75ed0f,
                            0x1b515143,
                            0x0990a659,
                            0xdcedb6b3,
                            0xec22de79,
                            0xdd56f7a9,
                            0x901194a6,
                            0x4bf3db02,
                            0x5d31787d,
                            0xd24da2ca,
                            0x9fc9bc14,
                            0x9aa38ac9,
                            0xe95972ba,
                            0x8233a732,
                            0xb9d4317e,
                            0x51f9b329,
                            0x94f12c56,
                            0x1ace26e4,
                            0xecda5183,
                            0x1353e547,
                            0x39b99ab3,
                            0x6413ac97,
                            0xeb6b5334,
                            0xdd94ed2b,
                            0x298e9d2c,
                            0xd38abc91,
                            0x3f17ee4e,
                            0x99f8931d,
                            0x88bae7da,
                            0xb5506a36,
                            0x2d7baf6d,
                            0x42a98d2b,
                            0xbb9b94b9,
                            0x58820083,
                            0x521bba4c,
                            0x76699597,
                            0x137b86be,
                            0x8533888e,
                            0xb37316dd,
                            0x284c3de4,
                            0xfe60e3e6,
                            0x94edaa40,
                            0x919c85cd,
                            0x24cb6f23,
                            0x6b446fbd,
                            0xbe933c15,
                            0x2a43951a,
                            0x791a9f90,
                            0x47977c04,
                            0xa6350eec,
                            0x95e817a5,
                            0xffc82e8c,
                            0xad379229,
                            0x6ec9531a,
                            0x8cab29f9,
                            0xb2f18402,
                            0xd0ebdac1,
                            0xd7b559b4,
                            0x7ad30e7c,
                            0xe1d1adb7,
                            0x58a66f9c,
                            0x7a26636a,
                            0x8c865f92,
                            0x65363517,
                            0x732b87db,
                            0x64a1ad52,
                            0x72e87c39,
                            0x0b943e4d,
                            0x532d3593,
                            0xedcf9975,
                            0x44b5bec1,
                            0x13ac91f8,
                            0x6e6f3a76,
                            0x36ac3c6d,
                            0x528a3ecf,
                            0xf3d8cd75,
                            0x8facd64c,
                            0xdb4d13d5,
                            0x80d49a67,
                            0xaa7061d3,
                            0x9486ba8d,
                            0x7454a65b,
                            0x18e7b707,
                            0xd9cc05b9,
                            0x44eb014d,
                            0x28ba26d8,
                            0xa8852791,
                            0xf8dc3053,
                            0xabe46b52,
                            0x9e261d1f,
                            0x768f83dd,
                            0x1c888838,
                            0x6d9b9ce6,
                            0x69e82575,
                            0x2959538f,
                            0xd0ff9685,
                            0x92b4540c,
                            0x7c93035b,
                            0x7cad90ad,
                            0x49aaa908,
                            0x3981f4b8,
                            0x191f4339,
                            0xd0971bfc,
                            0xa7209692,
                            0x0e253cad,
                            0x40e2ee61,
                            0xc5c63486,
                            0xdf4f238b,
                            0x2d3cb89a,
                            0x3b5704b2,
                            0xcc14c2cb,
                            0xb1698d38,
                            0x079c3b9b,
                            0xbb3867e4,
                            0x9f01e223,
                            0x35e69012,
                            0x5c87d888,
                            0x2cea4193,
                            0xee088da5,
                            0x0ea4d5ab,
                            0x8a4906e8,
                            0xf6e5e283,
                            0xee87fa18,
                            0x9f96c751,
                            0x947252c0,
                            0x9b50b97e,
                            0x05952521,
                            0x9440f5ae,
                            0xa0642786,
                            0xebcc62be,
                            0xadccf011,
                            0x00b863e6,
                            0x1c3ab5b3,
                            0x7c701e4b,
                            0xa9565792,
                            0xb1ad459c,
                            0x833ba164,
                            0x89544ae3,
                            0x35540c75,
                            0x198d0fec,
                            0xbe93bf33,
                            0xc28444b3,
                            0xbc3add48,
                            0xb4300c14,
                            0xee0ed408,
                            0xca08ada3,
                            0x0be06480,
                            0xc4dd8ce2,
                            0x61195564,
                            0x5b10a111,
                            0x65cd2b3b,
                            0xcbeb06ae,
                            0xfce70080,
                            0xef40b102,
                            0xfc0bfe6f,
                            0x8111bf20,
                            0xfb166db1,
                            0x3598b2ef,
                            0x1e0e04de,
                            0x1bf7cf2d,
                            0x0de7eaf1,
                            0x829457e0,
                            0xe8865341,
                            0x826272ad,
                            0xb57db2a4,
                            0x7413e6e7,
                            0x416323ff,
                            0x8e08d503,
                            0x1da4dfac,
                            0x983b9a78,
                            0x0fab5fe0,
                            0x585e7a90,
                            0x038cf73c,
                            0xecf90d31,
                            0x046055c8,
                            0x59926d71,
                            0x06959f1f,
                            0x3b8290b7,
                            0x0bb834d9,
                            0xa0dc5bec,
                            0xec9ae604,
                            0x6ebfd59d,
                            0xfeccbab5,
                            0x240bd4ba,
                            0x2df2b232,
                            0xe14e0383,
                            0xd86526ec,
                            0xe3d974fc,
                            0x940662b5,
                            0x81abf5d4,
                            0x8010e6eb,
                            0x700d9849,
                            0x040d0c42,
                            0xc980417b,
                            0x95fa374a,
                            0x724b1448,
                            0x217205ec,
                            0x0153b4bb,
                            0xea55ea92,
                            0x2049d5a1,
                            0x82576f06,
                            0x586fcfeb,
                            0xa975e489,
                            0x14c862e9,
                            0xacb8b52c,
                            0x2f3fb91e,
                            0xce273650,
                            0x66608f4a,
                            0x24f81bb7,
                            0x0382dc34,
                            0x07bdc163,
                            0xc42ad034,
                            0xe63cf998,
                            0x1a61f233,
                            0xd5754ebe,
                            0x37275214,
                            0x2322de2a,
                            0x3a53b9b4,
                            0xab9c6963,
                            0x2f3a51be,
                            0x5066e7c7,
                            0x941bda97,
                            0x75fadceb,
                            0xd05ad081,
                            0xf77d5daf,
                            0xd9879250,
                            0xebf8bf97,
                            0x65be4a70,
                            0x388eda48,
                            0x728173fb,
                            0x05975bfa,
                            0x314dad8a,
                            0x2cb4909f,
                            0xc736b716,
                            0x9007296d,
                            0x4fd61551,
                            0xd4378ccf,
                            0x649aac3e,
                            0xd9ca1a9d,
                            0x16ff16ae,
                            0x8090f1c5,
                            0xfe0c4703,
                            0xc4152307},
                    {0xf07e5e34,
                            0x62114ba6,
                            0xf45ffe22,
                            0xbaa48702,
                            0xe27e48a4,
                            0xc43b4779,
                            0x549a4566,
                            0x93bc4836,
                            0x3b2e8d46,
                            0x3f8a77ae,
                            0x71e2d944,
                            0xc09c5dce,
                            0xebfbfd4f,
                            0x7f8e1c40,
                            0x3c310a69,
                            0x52f62f09,
                            0xb7fd11bb,
                            0xa9d055a7,
                            0xe3bd4654,
                            0x9696ae10,
                            0xdf953225,
                            0x42fd2380,
                            0x69756e5c,
                            0x9d950bc4,
                            0xe2beea59,
                            0xd33daa07,
                            0xe97d31ce,
                            0xd9fb0a49,
                            0x553a27f2,
                            0x7166586f,
                            0xeb04d48c,
                            0x72adb63a,
                            0x340ab99e,
                            0x459b4609,
                            0x481421b7,
                            0x7db83c71,
                            0x192f6c22,
                            0x711852a8,
                            0xc6bd6562,
                            0xb91be2c8,
                            0xefe89dbf,
                            0xc404eb9b,
                            0x9ebc1bc7,
                            0x8dc7eed2,
                            0x4d84efd7,
                            0x0783d7e5,
                            0x3b5ca2f2,
                            0x9997e51c,
                            0x89b432c9,
                            0x72ae9672,
                            0x61d522d9,
                            0xa639fd45,
                            0xa7da3b46,
                            0x696e73ec,
                            0x89581a95,
                            0x4aa25f94,
                            0xd0eb2a48,
                            0x04865f68,
                            0x1cbd651a,
                            0xd6b2afd9,
                            0xd401b965,
                            0xd20aa5a7,
                            0xc0aa1b15,
                            0xfb4ce7af,
                            0x159974c5,
                            0x15d0841d,
                            0x6b2836b4,
                            0xef3b3edf,
                            0xaf2db0b3,
                            0x13106fb6,
                            0xff41d7f9,
                            0xab2a698d,
                            0x68e04dc9,
                            0xe5ee0099,
                            0xe50d4017,
                            0x5ea78d6d,
                            0x2e18fb07,
                            0xfe22b9ff,
                            0x544c05f1,
                            0xc2e10853,
                            0x8d151bd6,
                            0x17ee763a,
                            0xa663ce31,
                            0x4a4b5e33,
                            0x298b13c1,
                            0xd3b40c89,
                            0x121b6b4e,
                            0x59cf0429,
                            0x3d0bab9d,
                            0xd24c5dfe,
                            0x5bb7349f,
                            0xac5dbfe9,
                            0x7eca5ebb,
                            0xadb8b3e3,
                            0x71ab540b,
                            0xc8e3dc0d,
                            0x12e6cd3f,
                            0x8197f22c,
                            0x5ff77265,
                            0xe5641dbc,
                            0x818ab24c,
                            0x627b98f7,
                            0xdd84e1d6,
                            0x531c2346,
                            0xec2f4e3c,
                            0x4a3cb318,
                            0x70cb24fe,
                            0x35c17bfe,
                            0xec91fd18,
                            0x6efb3c18,
                            0x16908369,
                            0x41732188,
                            0x449e658b,
                            0x2e9931cb,
                            0x67cd066e,
                            0x883ca306,
                            0xf66aecac,
                            0x979bf015,
                            0x8e85e27d,
                            0x0560372b,
                            0x987995d6,
                            0xaff98ed7,
                            0x552ee87b,
                            0x21a53787,
                            0x3d3cfd45,
                            0xa084dae0,
                            0x8c91be2f,
                            0xac4c3550,
                            0xa7db63ff,
                            0x124b2f23,
                            0x95d05d4e,
                            0xb983db13,
                            0xa929a3c1,
                            0x111cd0a0,
                            0xf59ded9a,
                            0xce677ae3,
                            0xfa949e59,
                            0xd673e658,
                            0xf8c8e27b,
                            0x3c60fc3d,
                            0x59a4f230,
                            0xf54a5e87,
                            0x08cff440,
                            0xd4bbb1ee,
                            0x6a0c7db0,
                            0xecbaa99d,
                            0xec61dcaf,
                            0xf1056e2b,
                            0x54236899,
                            0xadad347c,
                            0xc9885bc9,
                            0x2fe2a4ec,
                            0x01ba2b86,
                            0x6b23f604,
                            0xb354ef08,
                            0x6a3dc5e2,
                            0xab61da36,
                            0x7543925a,
                            0x0a558940,
                            0x48d4d8f3,
                            0xd84f2f6f,
                            0x6ac5311c,
                            0xcd1b660e,
                            0x51293d3d,
                            0xa0f15790,
                            0xd629cd78,
                            0x89201fa5,
                            0x46005119,
                            0x9617fa14,
                            0xc375a68b,
                            0x7ccb519b,
                            0x6420a714,
                            0xb736d2ce,
                            0x154fcf4a,
                            0x71cad2f5,
                            0xacb150d7,
                            0x97bc8e36,
                            0xc5506d0a,
                            0xa9facc35,
                            0x1a9630db,
                            0xbd3d72ee,
                            0x58cdf27c,
                            0x17f3e1f9,
                            0x41598836,
                            0xd6adac30,
                            0x309a5b3f,
                            0x3bd3aa32,
                            0x40f08f50,
                            0xf37cbd6c,
                            0xcbdb8aef,
                            0xe0819189,
                            0x5a9b663b,
                            0x6932a448,
                            0xb1b3e866,
                            0xc50ee24d,
                            0xad999126,
                            0xafb04056,
                            0xc95974e5,
                            0x636a64fa,
                            0x0bb12dd9,
                            0x78caa164,
                            0xd26a7ec8,
                            0x451a0b53,
                            0x6d00aac6,
                            0x484d1d9d,
                            0x39728dd4,
                            0xfbfec2ea,
                            0xa6d5aaf9,
                            0x91c4f6ea,
                            0x31cab009,
                            0x9b6ba4e8,
                            0xe271ed67,
                            0x4c87a84d,
                            0x8a1a4567,
                            0x93749497,
                            0xc566edcc,
                            0xc8229554,
                            0x927925fd,
                            0xad1caced,
                            0xdc24f7ed,
                            0xc92b9220,
                            0x936cd037,
                            0xbd2d0256,
                            0x5c92409b,
                            0xa3aa2682,
                            0x4da97646,
                            0xbcfdec81,
                            0x25d5b61d,
                            0x20e1660d,
                            0x4b5214ed,
                            0x91aa596a,
                            0xb241415c,
                            0x88ec91a1,
                            0x2375e939,
                            0x981ad627,
                            0x4a54ee18,
                            0x13d98660,
                            0x9375c64d,
                            0x538d3b28,
                            0x4bf37ca7,
                            0x192b351e,
                            0x3cacf215,
                            0x3ecf3565,
                            0x50f5c0fc,
                            0xaafe3d4e,
                            0x6351b4f5,
                            0x1b800d4f,
                            0xfad73cdf,
                            0xe300e1d8,
                            0xb2cb5b04,
                            0xfb019702,
                            0xfb647f85,
                            0x375a7b74,
                            0xed6a6760,
                            0x45c54e76,
                            0x06524d79},
                    {0x48722ec4,
                            0x8a2694db,
                            0x3cf80478,
                            0xf9bc47ba,
                            0x76b258fb,
                            0xf71a1ec6,
                            0x841189df,
                            0x1a866461,
                            0x72b5488c,
                            0x71663983,
                            0xbda59407,
                            0xa2b68f85,
                            0x62dbd0aa,
                            0xe4966aa3,
                            0x32e0efaa,
                            0x71bb3699,
                            0x2eda14a6,
                            0x53f8917c,
                            0x874974ce,
                            0xe680bcca,
                            0x96a9c462,
                            0x399ca451,
                            0xc46616f5,
                            0xeee71114,
                            0x5878e472,
                            0x3a83c559,
                            0x54862a18,
                            0x82aea480,
                            0x492d0019,
                            0xd62a7027,
                            0x36655f50,
                            0xce412fdf,
                            0xc8136871,
                            0xd6cfe1d8,
                            0x121c9c91,
                            0x13abbf51,
                            0x3aaa7037,
                            0x9f6e7cb6,
                            0xae82c4c4,
                            0x55fdce32,
                            0xd8dd6bda,
                            0xd6ec4938,
                            0x6a5aee52,
                            0x52c8a764,
                            0xa6a85297,
                            0x5131de9e,
                            0x396a6599,
                            0xe27b1100,
                            0xe68588d3,
                            0x7b89a612,
                            0xad48a7a4,
                            0xfd205673,
                            0x81807089,
                            0x239d2d38,
                            0x39518df3,
                            0x256f3f14,
                            0x5c65e7b8,
                            0x64caebdc,
                            0xd8d694b6,
                            0xb4a87da3,
                            0xa651881e,
                            0xca1d252d,
                            0x993a3ddc,
                            0x14f9a54d,
                            0x6b14d2ff,
                            0xbbed03bb,
                            0x8d12bc03,
                            0x6cce455d,
                            0x613d6487,
                            0x6d04ce6a,
                            0xc2f4c84c,
                            0x306d8ff2,
                            0x584a9847,
                            0x68902fc5,
                            0x70af1a4f,
                            0x3ab4cb98,
                            0xe8be4453,
                            0x7e95d355,
                            0x84b0f371,
                            0x4c5ccb52,
                            0xdd6d029c,
                            0xafa47124,
                            0x71aabf91,
                            0xd3407f95,
                            0xe7fa3a9c,
                            0x4f634405,
                            0x0cbf2cb7,
                            0x0192ff17,
                            0x296959dd,
                            0x9e4d34d5,
                            0xfd9a4286,
                            0xac7b6933,
                            0x4650f585,
                            0x168af40d,
                            0x73816119,
                            0x5542d96d,
                            0x99047276,
                            0x1b5bbe67,
                            0x01a8209e,
                            0x6f9db32e,
                            0xd762bbd1,
                            0x299a3804,
                            0x87abe66d,
                            0xd479eeaa,
                            0x79928f4e,
                            0x3937ffbc,
                            0x3c8e83ca,
                            0x2a8f9347,
                            0x4d2324d3,
                            0xf0183dda,
                            0x9fbedb15,
                            0xac365889,
                            0xf1be552c,
                            0xa4b32d5a,
                            0xdc77fff3,
                            0x9d516da8,
                            0x7f3c347c,
                            0x39e8479f,
                            0x9e869687,
                            0x6a160347,
                            0x49ab7403,
                            0x830d31c7,
                            0x11311354,
                            0x79e6cc69,
                            0x35b25caa,
                            0x398af9aa,
                            0x02ef4356,
                            0xb5ecba53,
                            0x666d6c8b,
                            0x8836b3ae,
                            0x23b9fc98,
                            0x0cc8e3d0,
                            0x3ad594e1,
                            0xb124529d,
                            0xe059c1de,
                            0xfa88e0d9,
                            0xba117846,
                            0x1782a65a,
                            0xee9f80f9,
                            0xbc9aec55,
                            0x88aec1d4,
                            0x9c3907fa,
                            0x92b7b5bf,
                            0x464acbf4,
                            0xbbbd04a8,
                            0xf0e966bf,
                            0x14c5f971,
                            0x83018d49,
                            0xfaf4fc0a,
                            0x3b4639b2,
                            0x6b7e297d,
                            0xc0e9a807,
                            0x418713d3,
                            0x1a2b2361,
                            0x80850d90,
                            0xd515816e,
                            0x3deb48ea,
                            0x6bfe6aa1,
                            0x3680036c,
                            0x228e76ae,
                            0x78f16c87,
                            0xff4d85ea,
                            0x7d831974,
                            0xba962d6b,
                            0x4bae0b1d,
                            0xc0db431a,
                            0x04b46400,
                            0xcf427175,
                            0x244e321d,
                            0x1c8b1fc9,
                            0x63a2b794,
                            0x1939d9c6,
                            0xc92a530e,
                            0x21a8e5ad,
                            0x28050194,
                            0x3b106223,
                            0xb21e2ce1,
                            0x7ae71fe4,
                            0x7f7759f0,
                            0x0329c8f4,
                            0xd09f6b37,
                            0x897e12a5,
                            0x4103c4b1,
                            0x56520dae,
                            0x5d7391aa,
                            0x7ac9f12d,
                            0xeac6b834,
                            0x99f8f6a8,
                            0x2867867a,
                            0xff6f3343,
                            0x3167097a,
                            0x38432d1d,
                            0x108377f8,
                            0xfd8e0d5f,
                            0x25e15692,
                            0xf00d40f9,
                            0x1f1276f3,
                            0xb748c8cd,
                            0x6dbb9d9c,
                            0x99ab7ceb,
                            0xa4a9784f,
                            0xcb4b2535,
                            0xb3eb5ca7,
                            0xd3a09e75,
                            0x90f3ee7e,
                            0x28ef2a57,
                            0xbdb643a2,
                            0x1112ab10,
                            0x546b1af2,
                            0x8c41e90d,
                            0x0f5fcd88,
                            0x6f259f40,
                            0x34b33966,
                            0x5f3558d7,
                            0xfff36f0b,
                            0xa3459449,
                            0xdcecbce1,
                            0x69ff2bf7,
                            0x7525e1da,
                            0x24c9de72,
                            0xea9626b1,
                            0x87c7385d,
                            0x15e4211e,
                            0x9f7ef269,
                            0xfed018d1,
                            0x7632076c,
                            0x8d4f0157,
                            0x10c1205a,
                            0x65db0e00,
                            0x813f0e8b,
                            0xbafea255,
                            0xb47e6663,
                            0x2a0eba78,
                            0xf66b3783,
                            0xfff1db48,
                            0x47997f03,
                            0x3a49e877,
                            0x4536a0b5,
                            0x89b0738f,
                            0xf5758b5e,
                            0x1d277388,
                            0xf5db28e8,
                            0xb4ef0add,
                            0x776fed12,
                            0x045b614a,
                            0xc95f47ae,
                            0x13a1d602,
                            0x217d6338,
                            0xc509d080,
                            0x006789de,
                            0xd891cccc,
                            0xb02f9980,
                            0x67f00301,
                            0xafc87999,
                            0x043d8fbd,
                            0xb32d6061}};
}
